package HuffmanTree;

import HuffmanTree.pojo.huffmanTree;

import java.util.*;

/**
 * <p>哈夫曼树</p>
 * <p>哈夫曼树常用于数据压缩和加密等，你可以在现代密码学的很多地方看到哈夫曼树的影子</p>
 * <p>笔者结合自己的理解使用较为简单的方式（堆+递归）实现，
 * 可能与网上的资料和书本教材有一定出入，但总体的原理是一样的
 * 哈夫曼树总体实现并不困难，但是其中有很多细节问题需要注意，
 * 笔者一开始也有很多地方遗漏然后一点点debug（蒟蒻低头）</p>
 *
 * @author 没天赋
 * @since 2025-03-10
 */
public class method {
    public static Scanner sc = new Scanner(System.in);
    // 节点个数
    public static int n;
    // 最大节点个数
    public static final int N = 105;
    // 权值
    public static int[] values = new int[N];
    // 字符
    public static char[] nums = new char[N];
    // 哈夫曼树根节点
    public static huffmanTree root = new huffmanTree();
    // 优先队列,笔者认为这一步是哈夫曼树的精髓，（网上有的资料也使用自定义find函数，不过笔者认为使用堆会更加简单易懂）
    public static PriorityQueue<huffmanTree> queue = new PriorityQueue<>(Comparator.comparingInt(huffmanTree::getValue));
    // 创建哈夫曼字符的对应编码表
    public static Map<Character, String> huffmanCode = new HashMap<>();

    public static void main(String[] args) {
        n = sc.nextInt();
        for (int i = 1; i <= n; i++) {
            // 输入权值和字符
            values[i] = sc.nextInt();
            nums[i] = sc.next().charAt(0);
        }
        // 创建哈夫曼树
        root = createHuffmanTree();
        // 构建哈夫曼编码
        createHuffmanCode(root, "");
        // 输出哈夫曼编码
        huffmanCode.forEach((num, code) -> {
            System.out.println(num + " : " + code);
        });
    }

    /**
     * 创建哈夫曼树
     *
     * @return root
     */
    public static huffmanTree createHuffmanTree() {
        // 初始化结点
        for (int i = 1; i <= n; i++) {
            // 初始化结点
            huffmanTree tree = new huffmanTree();
            tree.setValue(values[i]);
            tree.setIndex(i);
            // 将结点加入优先队列
            queue.offer(tree);
        }
        // 循环创建哈夫曼树，直到队列中只有一个结点为止
        while (queue.size() > 1) {
            huffmanTree tree1 = queue.poll();
            huffmanTree tree2 = queue.poll();
            // 建立父节点
            huffmanTree tree = new huffmanTree(tree1.getValue() + tree2.getValue(), tree1, tree2, null, 0);
            // 让子节点指向父节点（这一步注意不能落下！！！）
            tree1.setParent(tree);
            tree2.setParent(tree);
            // 将结点加入优先队列
            queue.offer(tree);
        }
        // 返回最后一个节点即为根节点
        return queue.poll();
    }

    /**
     * 构建哈夫曼编码
     *
     * @param root
     * @param code
     */
    public static void createHuffmanCode(huffmanTree root, String code) {
        // 递归出口
        if (root.getLeft() == null && root.getRight() == null) {
            huffmanCode.put(nums[root.getIndex()], code);
            return;
        }
        // 分别向左右递归，注意一定要判空
        if (root.getLeft() != null) {
            createHuffmanCode(root.getLeft(), code + "0");
        }
        if (root.getRight() != null) {
            createHuffmanCode(root.getRight(), code + "1");
        }
    }
}
/**
 * 测试数据：
 * 8
 * 5 A
 * 29 B
 * 7 C
 * 8 D
 * 14 E
 * 23 F
 * 3 G
 * 11 H
 * ------
 * A : 0001
 * B : 11
 * C : 1010
 * D : 1011
 * E : 100
 * F : 01
 * G : 0000
 * H : 001
 */